Problem statement: zenit13skj

Súčasná ekonomická situácia v Európe rozhodne nie je radostná. Hromada veriteľov, ešte viac dlžníkov a nikde žiadne istoty! Aby sa Maroško trošku zdokonalil v ekonómii, rozhodol sa modelovať situáciu pomocou ľudí, ktorí majú voči sebe podĺžnosti a pomocou svojich finančných možností ich majú čo najjednoduchším spôsobom vyrovnať. Aby to nebolo príliš zložité, na úvod sa rozhodol uvažovať troch kamarátov - Anastáziu, Blažeja a Cypriána. Napíšte Maroškovi program, ktorý mu bude kontrolovať správnosť jeho ekonomických riešení!

V obehu sú mince s hodnotou 1 a 2 a bankovky s hodnotami 5, 10, 20 a 100 . Vstup pozostáva zo štyroch riadkov. Na prvom riadku sú tri čísla AB, BC a CA: suma, ktorú dlží Anastázia Blažejovi, suma, ktorú dlží Blažej Cypriánovi a suma, ktorú dlží Cyprián Anastázii. Ak je prvé číslo napríklad 50, potom to znamená, že Anastázia dlží Blažejovi 50 . Tieto čísla ale môžu byť aj záporné. Ak je napríklad prvé z nich -50, potom to označuje, že Blažej dlží Anastázii 50 . Všetky tieto čísla sú celé a nepresahujú v absolútnej hodnote 1000.

Na každom z ďalších troch riadkov je popísaná finančná situácia účastníkov. Prvý riadok popisuje Anastáziu, druhý Blažeja a tretí Cypriána. Jeden riadok pozostáva zo šiestich čísel: počet jednotlivých kusov platidiel, ktoré daný človek vlastní. Prvé číslo je počet jednoeurových mincí, druhé dvojeurových a tak ďalej v rastúcom poradí nominálnej hodnoty. Môžete predpokladať, že súčet kusov platidiel všetkých troch nepresahuje 100 a že ich celková hodnota nepresahuje 1000.

Naším cieľom je zistiť, či sú schopní účastníci vyrovnať podĺžnosti a ak áno, nájsť najmenší počet platidiel, ktoré pri vyrovnávaní nutne zmení majiteľa. Napríklad, ak A dlží B 70 , tak mu môže dať tri dvadsiatky a jednu desiatku. Dá sa to ale riešiť aj tak, že A dá B stovku a B mu vydá jednu dvadsiatku a jednu desiatku. Druhý spôsob považujeme za jednoduchší, pretože pri ňom menia majiteľa len tri kusy platidiel, zatiaľ čo v prvom prípade to boli štyri. Samozrejme, dôležité je, aby účastníci transakcií disponovali príslušnými platidlami.

Uveďme si ešte jeden príklad: nech A dlží B 20 a nech B dlží C tiež 20 (a C a A si nič nedlžia). Namiesto dvoch transakcií je výhodnejšie, ak A dá svojich 20 priamo C. Podobným spôsobom sa niekedy dá zjednodušiť výmena financí, ak je do transakcie zapojených viacero účastníkov.

Ak sa dajú podĺžnosti vyrovnať, vypíšte na výstup jediné číslo - minimálny počet platidiel, ktoré musia zmeniť majiteľa. Ak sa dlhy urovnať nedajú, vypíšte NEDA SA. V tejto úlohe je pamäťový limit 256 MB.

70 0 0
10 10 10 5 5 1
0 0 0 1 1 0
0 0 0 0 0 0
 

3
 

70 0 0
10 10 2 0 5 1
0 0 0 1 0 0
0 0 0 0 0 0
 

5
 

-20 -20 -20
3 2 1 0 1 0
4 4 4 1 0 0
10 4 3 0 0 1
 

0
 

7 -2 1
0 2 0 0 2 0
0 3 0 3 0 3
0 2 0 11 0 1
 

NEDA SA